import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class num17 {
    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if(digits.length() == 0) {
            return list;
        }
        Map<Character,String> map = new HashMap<Character,String>(){{
            put('2',"abc");
            put('3',"def");
            put('4',"ghi");
            put('5',"jkl");
            put('6',"mno");
            put('7',"pqrs");
            put('8',"tuv");
            put('9',"wxyz");
        }};
        dfs(list,map,digits,0,new StringBuilder());
        return list;
    }

    private void dfs(List<String> list, Map<Character,String> map,String digits, int i, StringBuilder s) {
        if(i == digits.length()) {
            list.add(s.toString());
        }else {
            char digit = digits.charAt(i);
            String letters = map.get(digit);
            int count = letters.length();
            for (int j = 0; j < count; j++) {
                s.append(letters.charAt(j));
                dfs(list, map, digits, i + 1, s);
                s.deleteCharAt(i);
            }
        }
    }
}
